﻿#include"stack_queue.h"


//基础实现
//1）队列的介绍	
// 先进先出，只能尾进，头出
//peek	pop	push	empty
	//链表实现
template <class T>
class my_queue1 {
private:
	struct ListNode{
		T data;
		ListNode* next;
	};

	ListNode* head;
	ListNode* tail;
	int size;

public:
	my_queue1():head(nullptr),tail(nullptr),size(0){}
	~my_queue1(){
		if (!empty())
		{
			ListNode* temp;
			while (head != tail) {
				temp = head;
				head = head->next;
				delete temp;
			}
		}
	}

	void push(T val) { 
		ListNode* temp = new ListNode; 
		temp->data = val; temp->next = nullptr;
		
		tail->next = temp; tail = temp;
	}
	void pop() { 
		ListNode* temp = head;
		head = head->next; 
		delete temp;
	}

	T peek() { return head->data; }

	bool empty() { return size == 0; }
};
	// 环形 n 长 T 数组实现
	//一般直接求余
	//修改为越界回到零 降低计算损耗
	//数据过量/为空 则返回入队失败或出队失败
template <class T>
class my_queue2 {
private:
	
	T* queue;
	int head;
	int tail;
	int size;
	int capacity;

public:
	my_queue2(int n) : size(0),head(0), tail(0), capacity(n) { queue = new T[n]; }
	~my_queue2() {delete queue;}

	bool push(T val) {
		if (full()) return false;
		queue[tail] = val;
		//tail = (tail + 1) % capacity;
		tail = tail == capacity ? 0 : (++tail);
		size++;
		return true;
	}
	bool pop() {
		if (empty()) return false;
		//head = (head + 1) % capacity;
		head = head == capacity ? 0 : (++head);
		size--;
		return true;
	}

	T peek() { return queue[head]; }

	bool empty() { return size == 0; }
	bool full() { return size == capacity; }
};

/*设计你的循环队列实现。
	循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。
	它也被称为“环形缓冲器”。循环队列的一个好处是我们可以利用这个队列之前用过的空间。
	在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。
	但是使用循环队列，我们能使用这些空间去存储新的值。
	你的实现应该支持如下操作：
	MyCircularQueue(k): 构造器，设置队列长度为 k 。
	Front: 从队首获取元素。如果队列为空，返回 -1 。
	Rear: 获取队尾元素。如果队列为空，返回 -1 。
	enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
	deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
	isEmpty(): 检查循环队列是否为空。
	isFull(): 检查循环队列是否已满。*/
	// 测试链接 : https://leetcode.cn/problems/design-circular-queue/
class MyCircularQueue {
private:
	int* queue;
	int head;
	int tail;
	int size;
	int capacity;
public:
	MyCircularQueue(int k) : size(0), head(0), tail(0), capacity(k) { queue = new int[k]; }

	bool enQueue(int value) {
		if (isFull()) return false;
		queue[tail] = value;
		tail = (tail + 1) == capacity ? 0 : (++tail);
		size++;
		return true;
	}

	bool deQueue() {
		if (isEmpty()) return false;
		head = (head + 1) == capacity ? 0 : (++head);
		size--;
		return true;
	}

	int Front() {
		if (isEmpty()) return -1;
		return queue[head];
	}

	int Rear() {
		if (isEmpty()) return -1;
		int n = tail == 0 ? (capacity - 1) : (tail - 1);
		return queue[n];
	}

	bool isEmpty() {
		return size == 0;
	}

	bool isFull() {
		return size == capacity;
	}
};


//2）栈的介绍	
// 先进后出，一个开口，头压 头弹
//top	pop	push empty
	//栈的数组实现
//未给定数据量	通过vector实现
template <class T>
class my_stack1 {
private:
	std::vector<T> stack;
public:
	my_stack1(int n) { stack.reserve(n); }
	void pop() { stack.pop_back(); }
	void push(T val) { stack.push_back(val); }

	T top() { return stack.back(); }

	bool empty() { return stack.empty(); }
	~my_stack1(){}
};
//给定数据量不会超过 n  int数组实现
class my_stack2 {
private:
	int* stack;
	int size;
public:
	my_stack2(int n) { stack = new int[n]; size = 0; }
	void pop() { size--; }
	void push(int val) { stack[size++] = val; }

	int top() { return stack[size - 1]; }

	bool empty() { return size == 0; }
	~my_stack2() { delete stack; }//?会报错
};

//栈与队列的相互实现
//队列
//仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
//实现 MyQueue 类：
//void push(int x) 将元素 x 推到队列的末尾
//int pop() 从队列的开头移除并返回元素
//int peek() 返回队列开头的元素	为空则 -1
//boolean empty() 如果队列为空，返回 true ；否则，返回 false
// 测试链接 : https://leetcode.cn/problems/implement-queue-using-stacks/
class MyQueue {
private:
	std::stack<int> in;
	std::stack<int> out;
public:

	MyQueue() {

	}

	void push(int x) {
		in.push(x);
	}

	int pop() {
		if (out.empty()) 
		while (!in.empty()) { out.push(in.top()); in.pop();}
		int n = out.top();
		out.pop();
		return n;
	}

	int peek() {
		if (empty())return -1;
		else if (out.empty())
			while (!in.empty()) { out.push(in.top()); in.pop(); }
		int n = out.top();
		return n;
	}

	bool empty() {
		return in.empty() && out.empty();
	}
};


//栈
//请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
//实现 MyStack 类：
//void push(int x) 将元素 x 压入栈顶。
//int pop() 移除并返回栈顶元素。
//int top() 返回栈顶元素。
//boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
// // 测试链接 : https://leetcode.cn/problems/implement-stack-using-queues/
class MyStack {
private:
	std::queue<int> que;
public:
	MyStack() {

	}

	void push(int x) {
		int n = que.size();
		que.push(x);
		while (n--) { que.push(que.front()); que.pop(); }
	}

	int pop() {
		int n = que.front();
		que.pop();
		return n;
	}

	int top() {
		return que.front();
	}

	bool empty() {
		return que.empty();
	}
};


// 最小栈
//设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
//实现 MinStack 类:
//MinStack() 初始化栈对象。
//void push(int val) 将元素val推入堆栈。
//void pop() 删除栈顶部的元素。
//int top() 获取栈顶部的元素。
//int getMin() 获取栈中的最小元素。
// 测试链接 : https://leetcode.cn/problems/min-stack/
class MinStack {
private:
	std::stack<int> st;
	std::stack<int> minst;

public:
	MinStack() {

	}

	void push(int val) {
		st.push(val);
		if (minst.empty() || val < minst.top()) { minst.push(val); }
		else minst.push(minst.top());
	}

	void pop() {
		st.pop();
		minst.pop();
	}

	int top() {
		return st.top();
	}

	int getMin() {
		return minst.top();
	}
};


//双端队列(deque)
//1）双端队列的介绍
/*
实现 MyCircularDeque 类:
MyCircularDeque(int k) ：构造函数,双端队列最大为 k 。
boolean insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true ，否则返回 false 。
boolean insertLast() ：将一个元素添加到双端队列尾部。如果操作成功返回 true ，否则返回 false 。
boolean deleteFront() ：从双端队列头部删除一个元素。 如果操作成功返回 true ，否则返回 false 。
boolean deleteLast() ：从双端队列尾部删除一个元素。如果操作成功返回 true ，否则返回 false 。
int getFront() )：从双端队列头部获得一个元素。如果双端队列为空，返回 -1 。
int getRear() ：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1 。
boolean isEmpty() ：若双端队列为空，则返回 true ，否则返回 false  。
boolean isFull() ：若双端队列满了，则返回 true ，否则返回 false 。
*/
// 测试链接 : https://leetcode.cn/problems/design-circular-deque/
//2）双端队列用双链表的实现
class MyCircularDeque1 {
private:
	std::list<int> L;
	int size;
	int capacity;
public:
	MyCircularDeque1(int k) {
		capacity = k; size = 0;
	}

	bool insertFront(int value) {
		if (isFull()) return false;
		else {
			L.push_front(value);
			size++;
			return true;
		}
	}

	bool insertLast(int value) {
		if (isFull()) return false;
		else {
			L.push_back(value);
			size++;
			return true;
		}
	}

	bool deleteFront() {
		if (isEmpty()) return false;
		else {
			L.pop_front();
			size--;
			return true;
		}
	}

	bool deleteLast() {
		if (isEmpty()) return false;
		else {
			L.pop_back();
			size--;
			return true;
		}
	}

	int getFront() {
		if (isEmpty()) return -1;
		return L.front();
	}

	int getRear() {
		if (isEmpty()) return -1;
		return L.back();
	}

	bool isEmpty() {
		return size == 0;
	}

	bool isFull() {
		return size == capacity;
	}
};
//3）双端队列用固定数组的实现
//循环数组队列

class MyCircularDeque2 {
private:
	int* arr;
	int front;
	int tail;
	int size;
	int capacity;
public:
	MyCircularDeque2(int k) {
		front = 0;
		tail = 0;
		size = 0;
		capacity = k;
		arr = new int[k];
	}

	bool insertFront(int value) {
		if (isFull())return false;
		else {
			front = front == 0 ? (capacity - 1) : (front - 1);
			arr[front] = value;
			size++;
			return true;
		}
	}

	bool insertLast(int value) {
		if (isFull())return false;
		else {
			arr[tail] = value;
			tail = tail == (capacity - 1) ? 0 : (tail + 1);
			size++;
			return true;
		}
	}

	bool deleteFront() {
		if (isEmpty())return false;
		else {
			front = front == (capacity - 1) ? 0 : (front + 1);
			size--;
			return true;
		}
	}

	bool deleteLast() {
		if (isEmpty())return false;
		else {
			tail = tail == 0 ? (capacity - 1) : (tail - 1);
			size--;
			return true;
		}
	}

	int getFront() {
		if (isEmpty()) return -1;
		return arr[front];
	}

	int getRear() {
		if (isEmpty()) return -1;
		int n = tail == 0 ? (capacity - 1) : (tail - 1);
		return arr[n];
	}

	bool isEmpty() {
		return size == 0;
	}

	bool isFull() {
		return size == capacity;
	}
};


